home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / kernel / utils / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-12-19  |  15.2 KB  |  646 lines
  1. /* hash.c --
  2.  *
  3.  *     This module contains routines to manipulate a hash table.
  4.  *     See hash.h for a definition of the structure of the hash
  5.  *     table.  Hash tables grow automatically as the amount of
  6.  *     information increases.
  7.  *
  8.  *    None of the routines in this module do any sort of mutual exclusion
  9.  *    of accesses to the hash tables.
  10.  *
  11.  * Copyright (C) 1983 Regents of the University of California
  12.  * All rights reserved.
  13.  */
  14.  
  15. #ifndef lint
  16. static char rcsid[] = "$Header: /cdrom/src/kernel/Cvsroot/kernel/utils/hash.c,v 9.2 90/09/11 14:11:36 kupfer Exp $ SPRITE (Berkeley)";
  17. #endif  not lint
  18.  
  19. #include "sprite.h"
  20. #include "hash.h"
  21. #include "stdlib.h"
  22. #include "string.h"
  23. #include "list.h"
  24. #include "sys.h"
  25. #include "bstring.h"
  26. #include <stdio.h>
  27.  
  28. /* 
  29.  * Forward declarations:
  30.  */
  31.  
  32. static Hash_Entry *ChainSearch _ARGS_((Hash_Table *table, Address key,
  33.                          List_Links *hashList));
  34. static int Hash _ARGS_((Hash_Table *table, char *key));
  35. static void RebuildTable _ARGS_((Hash_Table *table));
  36.  
  37. /* 
  38.  * The following defines the ratio of # entries to # buckets
  39.  * at which we rebuild the table to make it larger.
  40.  */
  41.  
  42. static rebuildLimit = 3;
  43.  
  44.  
  45. /*
  46.  *---------------------------------------------------------
  47.  * 
  48.  * Hash_Init --
  49.  *
  50.  *    This routine just sets up the hash table.
  51.  *
  52.  * Results:    
  53.  *    None.
  54.  *
  55.  * Side Effects:
  56.  *    Memory is allocated for the initial bucket area.
  57.  *
  58.  *---------------------------------------------------------
  59.  */
  60.  
  61. void
  62. Hash_Init(table, numBuckets, ptrKeys)
  63.     register Hash_Table    *table;
  64.     int            numBuckets;    /* How many buckets to create for 
  65.                      * starters. This number is rounded up 
  66.                      * to a power of two. */
  67.     int             ptrKeys;    /* 0 means that key values passed to 
  68.                      * HashFind will be strings, passed via
  69.                      * a (char *) pointer.  1 means that 
  70.                      * key values will be any one-word 
  71.                      * value passed as Address.  > 1 means 
  72.                      * that key values will be multi-word 
  73.                      * values whose address is passed as 
  74.                      * Address.  In this last case, ptrKeys 
  75.                      * is the number of words in the key, 
  76.                      * not the number of bytes. */
  77. {
  78.     register    int         i;
  79.     register    Hash_Bucket     *tablePtr;
  80.  
  81.     /* 
  82.      * Round up the size to a power of two. 
  83.      */
  84.  
  85.     if (numBuckets < 0) {
  86.     numBuckets = -numBuckets;
  87.     }
  88.     table->numEntries = 0;
  89.     table->version = 0;
  90.     table->ptrKeys = ptrKeys;
  91.     table->size = 2;
  92.     table->mask = 1;
  93.     table->downShift = 29;
  94.     while (table->size < numBuckets) {
  95.     table->size <<= 1;
  96.     table->mask = (table->mask << 1) + 1;
  97.     table->downShift--;
  98.     }
  99.  
  100.     table->table = (Hash_Bucket *) malloc(sizeof(Hash_Bucket) * table->size);
  101.     for (i=0, tablePtr = table->table; i < table->size; i++, tablePtr++) {
  102.     List_Init(&(tablePtr->list));
  103.     tablePtr->version = 0;
  104.     }
  105. }
  106.  
  107.  
  108. /*
  109.  *---------------------------------------------------------
  110.  *
  111.  * Hash --
  112.  *    This is a local procedure to compute a hash table
  113.  *    bucket address based on a string value.
  114.  *
  115.  * Results:
  116.  *    The return value is an integer between 0 and size - 1.
  117.  *
  118.  * Side Effects:    
  119.  *    None.
  120.  *
  121.  * Design:
  122.  *    It is expected that most keys are decimal numbers,
  123.  *    so the algorithm behaves accordingly.  The randomizing
  124.  *    code is stolen straight from the rand library routine.
  125.  *
  126.  *---------------------------------------------------------
  127.  */
  128.  
  129. static int
  130. Hash(table, key)
  131.     register Hash_Table *table;
  132.     register char     *key;
  133. {
  134.     register int     i = 0;
  135.     register int     j;
  136.     register unsigned     *intPtr;
  137.  
  138.     switch (table->ptrKeys) {
  139.     case 0:
  140.         while (*key != 0) {
  141.         i = (i * 10) + (*key++ - '0');
  142.         }
  143.         break;
  144.     case 1:
  145.         i = (int) key;
  146.         break;
  147.     case 2:
  148.         i = ((unsigned *) key)[0] + ((unsigned *) key)[1];
  149.         break;
  150.     default:
  151.         j = table->ptrKeys;
  152.         intPtr = (unsigned *) key;
  153.         do { 
  154.         i += *intPtr++; 
  155.         j--;
  156.         } while (j > 0);
  157.         break;
  158.     }
  159.  
  160.  
  161.     return(((i*1103515245 + 12345) >> table->downShift) & table->mask);
  162. }
  163.  
  164.  
  165. /*
  166.  *---------------------------------------------------------
  167.  *
  168.  * ChainSearch --
  169.  *
  170.  *     Search the hash table for the entry in the hash chain.
  171.  *
  172.  * Results:
  173.  *    Pointer to entry in hash chain, NIL if none found.
  174.  *
  175.  * Side Effects:
  176.  *    None.
  177.  *
  178.  *---------------------------------------------------------
  179.  */
  180.  
  181. static Hash_Entry *
  182. ChainSearch(table, key, hashList)
  183.     Hash_Table         *table;    /* Hash table to search. */
  184.     register Address    key;    /* A hash key. */
  185.     register List_Links *hashList;
  186. {
  187.     register Hash_Entry *hashEntryPtr;
  188.     register unsigned     *hashKeyPtr;
  189.     unsigned         *keyPtr;
  190.     register int    numKeys;
  191.  
  192.     numKeys = table->ptrKeys;
  193.     LIST_FORALL(hashList, (List_Links *) hashEntryPtr) {
  194.     switch (numKeys) {
  195.         case 0:
  196.         if (strcmp(hashEntryPtr->key.name, key) == 0) {
  197.             return(hashEntryPtr);
  198.         }
  199.         break;
  200.         case 1:
  201.         if (hashEntryPtr->key.ptr == key) {
  202.             return(hashEntryPtr);
  203.         }
  204.         break;
  205.         case 2:
  206.         hashKeyPtr = hashEntryPtr->key.words;
  207.         keyPtr = (unsigned *) key;
  208.         if (hashKeyPtr[0] == keyPtr[0] && hashKeyPtr[1] == keyPtr[1]) {
  209.             return(hashEntryPtr);
  210.         }
  211.         break;
  212.         default:
  213.         if (bcmp((Address) hashEntryPtr->key.words,
  214.              (Address) key,
  215.              numKeys * sizeof(int)) == 0) {
  216.             return(hashEntryPtr);
  217.         }
  218.         break;
  219.     }
  220.     }
  221.  
  222.     /* 
  223.      * The desired entry isn't there 
  224.      */
  225.  
  226.     return ((Hash_Entry *) NIL);
  227. }
  228.  
  229.  
  230.  
  231. /*
  232.  *---------------------------------------------------------
  233.  *
  234.  * Hash_LookOnly --
  235.  *
  236.  *     Searches a hash table for an entry corresponding to string.
  237.  *
  238.  * Results:
  239.  *    The return value is a pointer to the entry for string,
  240.  *    if string was present in the table.  If string was not
  241.  *    present, NIL is returned.
  242.  *
  243.  * Side Effects:
  244.  *    None.
  245.  *
  246.  *---------------------------------------------------------
  247.  */
  248.  
  249. Hash_Entry *
  250. Hash_LookOnly(table, key)
  251.     register Hash_Table *table;    /* Hash table to search. */
  252.     Address         key;    /* A hash key. */
  253. {
  254.     return(ChainSearch(table, key, &(table->table[Hash(table, key)].list)));
  255. }
  256.  
  257.  
  258. /*
  259.  *---------------------------------------------------------
  260.  *
  261.  * Hash_Find --
  262.  *
  263.  *    Searches a hash table for an entry corresponding to
  264.  *    key.  If no entry is found, then one is created.
  265.  *
  266.  * Results:
  267.  *    The return value is a pointer to the entry for string.
  268.  *    If the entry is a new one, then the pointer field is
  269.  *    zero.
  270.  *
  271.  *    Side Effects:
  272.  *    Memory is allocated, and the hash buckets may be modified.
  273.  *---------------------------------------------------------
  274.  */
  275.  
  276. Hash_Entry *
  277. Hash_Find(table, key)
  278.     register    Hash_Table *table;    /* Hash table to search. */
  279.     Address            key;        /* A hash key. */
  280. {
  281.     register     unsigned     *hashKeyPtr;
  282.     register     unsigned     *keyPtr;
  283.     register     Hash_Bucket     *bucketPtr;
  284.     Hash_Entry            *hashEntryPtr;
  285.  
  286.     keyPtr = (unsigned *) key;
  287.  
  288.     bucketPtr = &(table->table[Hash(table, (Address) keyPtr)]);
  289.     hashEntryPtr = ChainSearch(table, (Address) keyPtr, &(bucketPtr->list));
  290.  
  291.     if (hashEntryPtr != (Hash_Entry *) NIL) {
  292.     return(hashEntryPtr);
  293.     }
  294.  
  295.     /* 
  296.      * The desired entry isn't there.  Before allocating a new entry,
  297.      * see if we're overloading the buckets.  If so, then make a
  298.      * bigger table.
  299.      */
  300.  
  301.     if (table->numEntries >= rebuildLimit * table->size) {
  302.     RebuildTable(table);
  303.     bucketPtr = &(table->table[Hash(table, (Address) keyPtr)]);
  304.     }
  305.     table->numEntries += 1;
  306.  
  307.     /*
  308.      * Not there, we have to allocate.  If the string is longer
  309.      * than 3 bytes, then we have to allocate extra space in the
  310.      * entry.
  311.      */
  312.  
  313.     switch (table->ptrKeys) {
  314.     case 0:
  315.         hashEntryPtr = (Hash_Entry *) malloc((sizeof(Hash_Entry) +
  316.                           strlen((Address) keyPtr) - 3));
  317.         (void)strcpy((char *) hashEntryPtr->key.name, (char *) keyPtr);
  318.         break;
  319.     case 1:
  320.         hashEntryPtr = (Hash_Entry *) malloc(sizeof(Hash_Entry));
  321.         hashEntryPtr->key.ptr = (Address) keyPtr;
  322.         break;
  323.     case 2:
  324.         hashEntryPtr = 
  325.         (Hash_Entry *) malloc(sizeof(Hash_Entry)
  326.             + sizeof(unsigned));
  327.         hashKeyPtr = hashEntryPtr->key.words;
  328.         *hashKeyPtr++ = *keyPtr++;
  329.         *hashKeyPtr = *keyPtr;
  330.         break;
  331.     default: {
  332.         register     n;
  333.  
  334.         n = table->ptrKeys;
  335.         hashEntryPtr = (Hash_Entry *) 
  336.             malloc((sizeof(Hash_Entry)
  337.                 + (n - 1) * sizeof(unsigned)));
  338.         hashKeyPtr = hashEntryPtr->key.words;
  339.         do { 
  340.         *hashKeyPtr++ = *keyPtr++; 
  341.         } while (--n);
  342.         break;
  343.     }
  344.     }
  345.  
  346.     hashEntryPtr->value = (Address) NIL;
  347.     hashEntryPtr->bucketPtr = bucketPtr;
  348.     List_Insert((List_Links *) hashEntryPtr, LIST_ATFRONT(&(bucketPtr->list)));
  349.     bucketPtr->version++;
  350.  
  351.     return(hashEntryPtr);
  352. }
  353.  
  354.  
  355.  
  356. /*
  357.  *---------------------------------------------------------
  358.  *
  359.  * Hash_Delete --
  360.  *
  361.  *     Delete the given hash table entry and free memory associated with
  362.  *    it.
  363.  *
  364.  * Results:
  365.  *    None.
  366.  *
  367.  * Side Effects:
  368.  *    Hash chain that entry lives in is modified and memory is freed.
  369.  *
  370.  *---------------------------------------------------------
  371.  */
  372.  
  373. void
  374. Hash_Delete(table, hashEntryPtr)
  375.     Hash_Table            *table;
  376.     register    Hash_Entry    *hashEntryPtr;
  377. {
  378.     if (hashEntryPtr != (Hash_Entry *) NIL) {
  379.     List_Remove((List_Links *) hashEntryPtr);
  380.     hashEntryPtr->bucketPtr->version++;
  381.     free((char *) hashEntryPtr);
  382.     table->numEntries--;
  383.     }
  384. }
  385.  
  386.  
  387. /*
  388.  *---------------------------------------------------------
  389.  *
  390.  * RebuildTable --
  391.  *    This local routine makes a new hash table that
  392.  *    is larger than the old one.
  393.  *
  394.  * Results:    
  395.  *     None.
  396.  *
  397.  * Side Effects:
  398.  *    The entire hash table is moved, so any bucket numbers
  399.  *    from the old table are invalid.
  400.  *
  401.  *---------------------------------------------------------
  402.  */
  403.  
  404. static
  405. void
  406. RebuildTable(table)
  407.     register    Hash_Table     *table;        /* Table to be enlarged. */
  408. {
  409.     register    Hash_Bucket    *oldTable;
  410.     register    Hash_Entry      *hashEntryPtr;
  411.     register    int         oldSize;
  412.     int              bucket;
  413.     Hash_Bucket             *saveTable;
  414.     Hash_Bucket             *bucketPtr;
  415.     int                 version;
  416.  
  417.     saveTable = table->table;
  418.     oldSize = table->size;
  419.     version = table->version + 1;
  420.  
  421.     /* 
  422.      * Build a new table 4 times as large as the old one. 
  423.      */
  424.  
  425.     Hash_Init(table, table->size * 4, table->ptrKeys);
  426.     table->version = version;
  427.  
  428.     for (oldTable = saveTable; oldSize > 0; oldSize--, oldTable++) {
  429.     while (!List_IsEmpty(&(oldTable->list))) {
  430.         hashEntryPtr = (Hash_Entry *) List_First(&(oldTable->list));
  431.         List_Remove((List_Links *) hashEntryPtr);
  432.         switch (table->ptrKeys) {
  433.         case 0:
  434.             bucket = Hash(table, (Address) hashEntryPtr->key.name);
  435.             break;
  436.         case 1:
  437.             bucket = Hash(table, (Address) hashEntryPtr->key.ptr);
  438.             break;
  439.         default:
  440.             bucket = Hash(table, (Address) hashEntryPtr->key.words);
  441.             break;
  442.         }
  443.         bucketPtr = &(table->table[bucket]);
  444.         List_Insert((List_Links *) hashEntryPtr, 
  445.         LIST_ATFRONT(&(bucketPtr->list)));
  446.         hashEntryPtr->bucketPtr = bucketPtr;
  447.         table->numEntries++;
  448.     }
  449.     }
  450.  
  451.     free((char *) saveTable);
  452. }
  453.  
  454.  
  455. /*
  456.  *---------------------------------------------------------
  457.  *
  458.  * HashStats --
  459.  *    This routine merely prints statistics about the
  460.  *    current bucket situation.
  461.  *
  462.  * Results:    
  463.  *    None.
  464.  *
  465.  * Side Effects:    
  466.  *    Junk gets printed.
  467.  *
  468.  *---------------------------------------------------------
  469.  */
  470.  
  471. void
  472. Hash_Stats(table)
  473.     Hash_Table *table;
  474. {
  475.     int count[10], overflow, i, j;
  476.     Hash_Entry     *hashEntryPtr;
  477.     List_Links    *hashList;
  478.  
  479.     for (i=0; i<10; i++) {
  480.     count[i] = 0;
  481.     }
  482.     overflow = 0;
  483.     for (i = 0; i < table->size; i++) {
  484.     j = 0;
  485.     hashList = &(table->table[i].list);
  486.     LIST_FORALL(hashList, (List_Links *) hashEntryPtr) {
  487.         j++;
  488.     }
  489.     if (j < 10) {
  490.         count[j]++;
  491.     } else {
  492.         overflow++;
  493.     }
  494.     }
  495.  
  496.     printf("Entries in table %d number of buckets %d\n", 
  497.         table->numEntries, table->size);
  498.     for (i = 0;  i < 10; i++) {
  499.     printf("Number of buckets with %d entries: %d.\n", i, count[i]);
  500.     }
  501.     printf("Number of buckets with > 9 entries: %d.\n", overflow);
  502. }
  503.  
  504.  
  505. /*
  506.  *---------------------------------------------------------
  507.  *
  508.  * Hash_StartSearch --
  509.  *
  510.  *    This procedure sets things up for a complete search
  511.  *    of all entries recorded in the hash table.
  512.  *
  513.  * Results:    
  514.  *    None.
  515.  *
  516.  * Side Effects:
  517.  *    The version number of the table is set to -1 so that the structure
  518.  *    will be initialized in the first Hash_Next.
  519.  *
  520.  *---------------------------------------------------------
  521.  */
  522.  
  523. void
  524. Hash_StartSearch(hashSearchPtr)
  525.     register Hash_Search *hashSearchPtr; /* Area in which to keep state 
  526.                         about search.*/
  527. {
  528.     hashSearchPtr->tableVersion = -1;
  529. }
  530.  
  531. /*
  532.  *---------------------------------------------------------
  533.  *
  534.  * Hash_Next --
  535.  *
  536.  *    This procedure returns successive entries in the hash table.
  537.  *
  538.  * Results:
  539.  *    The return value is a pointer to the next HashEntry
  540.  *    in the table, or NIL when the end of the table is
  541.  *    reached.
  542.  *
  543.  * Side Effects:
  544.  *    The information in hashSearchPtr is modified to advance to the
  545.  *    next entry.
  546.  *
  547.  *---------------------------------------------------------
  548.  */
  549.  
  550. Hash_Entry *
  551. Hash_Next(table, hashSearchPtr)
  552.     register Hash_Table  *table;     /* Table to be searched. */
  553.     register Hash_Search *hashSearchPtr; /* Area used to keep state about 
  554.                         search. */
  555. {
  556.     register List_Links *hashList;
  557.     register Hash_Entry *hashEntryPtr;
  558.     Hash_Bucket        *bucketPtr;
  559.  
  560.     /*
  561.      * Check version number of the hash table.
  562.      */
  563.     if (hashSearchPtr->tableVersion < table->version) {
  564.     hashSearchPtr->nextIndex = 0;
  565.     hashSearchPtr->hashEntryPtr = (Hash_Entry *) NIL;
  566.     hashSearchPtr->tableVersion = table->version;
  567.     }
  568.     hashEntryPtr = hashSearchPtr->hashEntryPtr;
  569.  
  570.     /* 
  571.      * Now check version number of the hash bucket.
  572.      */
  573.     if (hashEntryPtr != (Hash_Entry *) NIL &&
  574.     !List_IsAtEnd(hashSearchPtr->hashList, (List_Links *) hashEntryPtr) &&
  575.     hashEntryPtr->bucketPtr->version > hashSearchPtr->bucketVersion) {
  576.     hashEntryPtr = (Hash_Entry *) NIL;
  577.     hashSearchPtr->nextIndex--;
  578.     }
  579.  
  580.     while (hashEntryPtr == (Hash_Entry *) NIL ||
  581.        List_IsAtEnd(hashSearchPtr->hashList, (List_Links *) hashEntryPtr)) {
  582.     if (hashSearchPtr->nextIndex >= table->size) {
  583.         return((Hash_Entry *) NIL);
  584.     }
  585.     bucketPtr = &(table->table[hashSearchPtr->nextIndex]);
  586.     hashList = &(bucketPtr->list);
  587.     hashSearchPtr->bucketVersion = bucketPtr->version;
  588.     hashSearchPtr->nextIndex++;
  589.     if (!List_IsEmpty(hashList)) {
  590.         hashEntryPtr = (Hash_Entry *) List_First(hashList);
  591.         hashSearchPtr->hashList = hashList;
  592.         break;
  593.     }
  594.     }
  595.  
  596.     hashSearchPtr->hashEntryPtr = 
  597.         (Hash_Entry *) List_Next((List_Links *) hashEntryPtr);
  598.  
  599.     return(hashEntryPtr);
  600. }
  601.  
  602.  
  603. /*
  604.  *---------------------------------------------------------
  605.  *
  606.  * Hash_Kill --
  607.  *
  608.  *    This routine removes everything from a hash table
  609.  *    and frees up the memory space it occupied.
  610.  *
  611.  * Results:    
  612.  *    None.
  613.  *
  614.  * Side Effects:
  615.  *    Lots of memory is freed up.
  616.  *
  617.  *---------------------------------------------------------
  618.  */
  619.  
  620. void
  621. Hash_Kill(table)
  622.     Hash_Table *table;    /* Hash table whose space is to be freed */
  623. {
  624.     register    Hash_Bucket    *hashTableEnd;
  625.     register    Hash_Entry    *hashEntryPtr;
  626.     register    Hash_Bucket    *tablePtr;
  627.  
  628.     tablePtr = table->table;
  629.     hashTableEnd = &(tablePtr[table->size]);
  630.     for (; tablePtr < hashTableEnd; tablePtr++) {
  631.     while (!List_IsEmpty(&(tablePtr->list))) {
  632.         hashEntryPtr = (Hash_Entry *) List_First(&(tablePtr->list));
  633.         List_Remove((List_Links *) hashEntryPtr);
  634.         free((char *) hashEntryPtr);
  635.     }
  636.     }
  637.     free((char *) table->table);
  638.  
  639.     /*
  640.      * Set up the hash table to cause memory faults on any future
  641.      * access attempts until re-initialization.
  642.      */
  643.  
  644.     table->table = (Hash_Bucket *) NIL;
  645. }
  646.